#include <iostream>
#include <memory>
#include <stddef.h>
//
// Created by Asus on 2025/5/31.
//
using namespace std;

class ListNode {
public:
    int data;
    ListNode *next;

    ListNode() {
        data = 0;
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    int len;

    LinkList();

    ~LinkList();

    // 在链表的最后插入数据x
    void addNodeToEnd(int data);

    // 查找并返回第i个结点的指针
    ListNode *getPointer(int index);

    // 打印第i个结点的数据
    void getData(int index);

    // 在第i个位置插入一个data为item的结点
    void insertNode(int i, int item);

    // 删除第i个结点
    void deleteNode(int index);

    // 打印单链表中的所有结点
    void displayAllNodes();

    // 将单链表中第pa、pb个两个结点互换
    void swapNodes(int index1, int index2);

    // 单链表的排序
    void sortForLinkList();

    // 合并两个单链表，生成一个新的单链表并返回
    LinkList mergeLinkLists(LinkList &l1, LinkList &l2);

    // 单链表的整表删除
    void deleteLinkList(LinkList &l1);
};

LinkList::LinkList() {
    head = new ListNode();
    len = 0;
}

LinkList::~LinkList() {
    head = NULL;
}

void LinkList::addNodeToEnd(int data) {
    ListNode *l = new ListNode();
    l->data = data;
    if (head->next == NULL) {
        head->next = l;
    } else {
        ListNode *p;
        p = head;
        for (int k = 1; k <= len; k++) {
            p = p->next;
        }
        p->next = l;
    }
    len++;
}

ListNode *LinkList::getPointer(int i) {
    if (i <= 0 || i > len) {
        puts("error");
    } else {
        ListNode *p;
        p = head;
        for (int k = 1; k <= i; k++) {
            p = p->next;
        }
        return p;
    }
}

// 打印第i个结点的数据
void LinkList::getData(int i)
{
    if ((i <= 0) || (i > len))
    {
        puts("输出位置错误");
    }
    else
    {
        int x;
        x = getPointer(i)->data;
        printf("第 %d 个结点存储的数据是：%d \n", i, x);
    }
}

// 在第i个位置插入一个data为item的结点
void LinkList::insertNode(int i, int item) {
    if (i <= 0 || i > len) {
        puts("error");
    } else {
        ListNode *node = new ListNode();
        node->data = item;
        node->next = getPointer(i);
        getPointer(i-1)->next = node;
        len--;
    }
}

// 删除第i个结点
void LinkList::deleteNode(int i)
{
    if ((i <= 0) || (i > len))
    {
        puts("删除位置错误");
    }
    else
    {
        ListNode *nodeToDelete = getPointer(i);
        if (i == 1)
        {
            head->next = getPointer(2);
        }
        else if (i == len)
        {
            getPointer(i - 1)->next = NULL;
        }
        else
        {
            getPointer(i - 1)->next = getPointer(i + 1); // 把i的上一个结点点的指针指向i的下一个结点，就会在遍历中自动跳过第i个结点，相当于删除了第i个结点
        }
        delete nodeToDelete; // 释放被删除结点的内存
        len--;               // 删除了一个结点，链表的长度--
    }
}

void LinkList::displayAllNodes()
{
    ListNode *p;
    p = head;
    while (p->next != NULL)
    {
        p = p->next;
        cout << p->data << " ";
    }
    puts("");
}

// 将单链表中第pa、pb个两个结点互换
void LinkList::swapNodes(int pa, int pb)
{
    if (pa != pb && pa > 0 && pa <= len && pb > 0 && pb <= len) // 当两个结点的位置都合法时
    {
        // 获取pa、pb两个结点
        ListNode *p = getPointer(pa);
        ListNode *q = getPointer(pb);

        // 获取pa、pb的前驱结点（因为要改变交换结点和前一个结点的指针，所以需要前驱结点
        // GPT优化之后的代码，挺简洁的就抄了过来，把大量的ifelse判断转化成了三目的运算，之后可以借鉴
        ListNode *p_before = (pa == 1) ? NULL : getPointer(pa - 1); // 如果pa是第一个结点，p的前驱结点就是NULL，不是第一个的话，前驱是pa - 1
        ListNode *q_before = (pb == 1) ? NULL : getPointer(pb - 1);

        // 更新前驱结点的指针（指向交换后的结点）
        if (p_before)
            p_before->next = q; // if (p_before) 等价于 if (p_before != NULL)
        else
            head = q;
        if (q_before)
            q_before->next = p;
        else
            head = p;

        // 交换结点的指针
        ListNode *temp = p->next;
        p->next = q->next;
        q->next = temp;
    }
    else
        puts("结点不合法");
}

// 单链表的排序
void LinkList::sortForLinkList()
{
    // TODO: 把冒泡排序能否替换为更高效的排序
    for (int i = 1; i <= len; i++)
        for (int j = i; j <= len; j++)
            if (getPointer(i)->data > getPointer(j)->data)
                swapNodes(i, j);
}

// 合并两个单链表，生成一个新的单链表并返回
LinkList LinkList::mergeLinkLists(LinkList &La, LinkList &Lb)
{
    LinkList L; // 结果数组

    // 将La里的结点逐个插入L中
    ListNode *p;
    p = La.head;
    for (int i = 1; i <= La.len; i++)
    {
        p = p->next;
        L.insertNode(i, p->data);
    }

    // 将Lb里的结点逐个插入L中（采用了类似的头插法，Lb的第一个插入L的第一个位置，之后继续插入，Lb的最后一个的下一个是La的第一个）
    p = Lb.head;
    for (int i = 1; i <= Lb.len; i++)
    {
        p = p->next;
        L.insertNode(i, p->data);
    }

    // 给L排序
    L.sortForLinkList();

    return L;
}

// 单链表的整表删除
void LinkList::deleteLinkList(LinkList &L)
{
    ListNode *p;
    ListNode *q;
    p = head->next; // p指向第一个结点
    while (p != NULL)
    {
        q = p->next;
        delete p;
        p = q;
    }
    head = NULL; // 头指针置为空
}

class Resource {
public:
    Resource() {
        cout << "Resource" << endl;
    }

    ~Resource() {
        cout << "~Resource" << endl;
    }

    void use() {
        cout << "Use" << endl;
    }
};

void unique_ptr_demo() {
    cout << "unique_ptr" << endl;
    // 直接构造
    unique_ptr<Resource> ptr1(new Resource());
    ptr1->use();
    // make_unique
    unique_ptr<Resource> ptr2 = make_unique<Resource>();
    ptr2->use();

    unique_ptr<Resource> ptr3 = move(ptr2);
    if (!ptr2) {
        cout << "ptr2 is null after move\n" << endl;
    }

    ptr3.reset();
    cout << "ptr3 is null after move\n" << endl;
}

struct Node {
    int data;
    shared_ptr<Node> next;
    ~Node() { cout << "Node destroyed: " << data << "\n"; }
};

void shared_ptr() {
    auto node = make_shared<Node>();
}

int main(char *argv[]) {
    // 创建链表La: 3 -> 1 -> 2
    LinkList La;
    La.addNodeToEnd(3);
    La.addNodeToEnd(1);
    La.addNodeToEnd(2);
    cout << "La: ";
    La.displayAllNodes(); // 输出: 3 1 2

    // 创建链表Lb: 5 -> 4
    LinkList Lb;
    Lb.addNodeToEnd(5);
    Lb.addNodeToEnd(4);
    cout << "Lb: ";
    Lb.displayAllNodes(); // 输出: 5 4

    // 测试插入操作
    La.insertNode(2, 6); // 在位置2插入6
    cout << "La after insert at position 2: ";
    La.displayAllNodes(); // 输出: 3 6 1 2

    // 测试删除操作
    La.deleteNode(3); // 删除位置3的节点
    cout << "La after delete at position 3: ";
    La.displayAllNodes(); // 输出: 3 6 2

    // 测试获取数据
    La.getData(2); // 输出: 第 2 个结点存储的数据是：6

    // 测试交换节点
    La.swapNodes(1, 3); // 交换位置1和3的节点
    cout << "La after swap nodes 1 and 3: ";
    La.displayAllNodes(); // 输出: 2 6 3

    // 测试排序
    La.sortForLinkList();
    cout << "La after sorting: ";
    La.displayAllNodes(); // 输出: 2 3 6

    // 测试合并
    LinkList Lc = Lc.mergeLinkLists(La, Lb);
    cout << "Merged list Lc: ";
    Lc.displayAllNodes(); // 输出: 2 3 4 5 6

    unique_ptr_demo();
    if (!NULL) {
        printf("NULL\n");
    }

    // if (!nullptr) {
    //     printf("nullptr\n");
    // }
}
